package B刷题.暴力递归.A回溯;

/**
 * @author wei.zhao
 * @description: 79.单词搜索
 */
public class Code09_WordExist {

    /**
     * 思路：
     * 遍历二维数组，当前字符与字符串首字符一致的都可能是开始节点，分别从这些节点开始尝试；
     * 每次确定从当前节点出发的下一个节点是否满足条件，满足条件继续，所有字符确定完毕，返回true。
     * 注意点：
     * 使用数组记录相同位置的字符是否已经使用；
     * 不要忘记回溯，重置状态。
     */
    int[][] nears = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public boolean exist(char[][] board, String word) {
        boolean[][] used = new boolean[board.length][board[0].length];
        char fChar = word.charAt(0);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == fChar) {
                    used[i][j] = true;
                    boolean result = process(board, used, word, 1, i, j);
                    if (result) {
                        return result;
                    }
                    used[i][j] = false;
                }
            }
        }
        return false;
    }

    private boolean process(char[][] board, boolean[][] used, String word, int curP, int row, int col) {
        if (curP == word.length()) {
            return true;
        }
        for (int[] near : nears) {
            if (isValid(board, used, word, curP, row + near[0], col + near[1])) {
                used[row + near[0]][col + near[1]] = true;
                boolean result = process(board, used, word, curP + 1, row + near[0], col + near[1]);
                if (result) {
                    return true;
                }
                used[row + near[0]][col + near[1]] = false;
            }
        }
        return false;
    }

    private boolean isValid(char[][] board, boolean[][] used, String word, int curP, int row, int col) {
        if (row < 0 || row > board.length - 1
                || col < 0 || col > board[0].length - 1
                || word.charAt(curP) != board[row][col]
                || used[row][col]) {
            return false;
        }
        return true;
    }

}
